package codetop.microsoft.T494;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @Author: 18362
 * @Create: 2022-08-16 14:03:30 星期二
 */
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        queue1.offer(0);
        queue2.offer(1);
        for (int i=0; i<nums.length; ++i) {
            int size = queue1.size();
            Map<Integer, Integer> map = new HashMap<>();
            for (int j=0; j<size; ++j) {
                int value = queue1.poll(), cnt = queue2.poll();
                map.put(value - nums[i], map.getOrDefault(value - nums[i], 0) + cnt);
                map.put(value + nums[i], map.getOrDefault(value + nums[i], 0) + cnt);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                queue1.offer(entry.getKey());
                queue2.offer(entry.getValue());
            }
        }
        int res = 0;
        while (!queue1.isEmpty()) {
            int value = queue1.poll(), cnt = queue2.poll();
            if (value == target)
                res += cnt;
        }
        return res;
    }
}